from ListeChainee import *

class ListeChainee2(ListeChainee):
    """Improved version of ListeChainee (inheriting all its methods), implementation of merge sort for chained lists."""
    def __init__(self, *args):
        ListeChainee.__init__(self, *args)

    def merge(self, other):
        """
        Input lists must be sorted!
        other is modified during the process...

        Nested lists: it works!
        >>> x = ListeChainee2(1, 3, 5)
        >>> y = ListeChainee2(2, 4, 6)
        >>> x.tail.next = y.head
        >>> x.merge(y)
        >>> print x
        [1, 2, 3, 4, 5, 6]

        Empty other
        >>> x = ListeChainee2(1, 2)
        >>> y = ListeChainee2()
        >>> x.merge(y)
        >>> print x
        [1, 2]

        Empty self
        >>> x = ListeChainee2()
        >>> y = ListeChainee(1, 2)
        >>> x.merge(y)
        >>> print x
        [1, 2]

        Example
        >>> x = ListeChainee2(1, 3, 4, 8, 10)
        >>> y = ListeChainee2(2, 5, 9, 15)
        >>> x.merge(y)
        >>> print x
        [1, 2, 3, 4, 5, 8, 9, 10, 15]
        """
        sz = len(self)+len(other)
        first = p = None
        #we compare them as long as we can...
        while self.size!=0 and other.size!=0:
            #get a pointer to the smallest number's node
            if self.head.data<other.head.data:
                min = self.head
                self.head = self.head.next
                self.size -= 1
            else:
                min = other.head
                other.head = other.head.next
                other.size -= 1
            #we've got our next (or first) node...
            if p==None:
                p = first = min
            else:
                p.next = min
                p = min
        #don't forget remaining parts
        self.size = sz #always the same...
        if p==None: #is there any empty list?
            if other.size != 0:
                self.head = other.head
                self.tail = other.tail
            else:
                #other is empty,
                #there's nothing to do!
                pass
        else:
            #p now points to the current tail
            if other.size != 0:
                p.next = other.head #concat
                self.tail = other.tail #the real one
            else:
                p.next = self.head #concat
                #self.tail = self.tail
            #self.tail.next = None #close the chain
            self.head = first


if __name__=='__main__':
    import doctest
    doctest.testmod()
